# Darren
# 2025年02月22日11时21分02秒
import random
import time
import sys

sys.setrecursionlimit(100000)  # 设置递归深度


class Sort:
    def __init__(self, n, nums_range):
        self.n = n  # 序列元素个数
        self.arr = []  # 元素序列
        # self.arr = [76, 32, 1, 59, 29, 80, 88, 6, 79, 69]  # 测试用例
        self.nums_range = nums_range  # 数字范围
        self.random_nums()  # 序列生成函数

    def random_nums(self):
        for x in range(self.n):
            self.arr.append(random.randint(1, self.nums_range - 1))

    def partition(self, left, right):  # 划分
        i, j = left, right
        pivot = self.arr[i]  # 枢轴元素
        while i < j:
            while i < j and self.arr[j] >= pivot:
                j -= 1  # 从右往左找到第一个小于pivot的元素
            self.arr[i] = self.arr[j]  # 交换
            while i < j and self.arr[i] <= pivot:
                i += 1  # 从左向右找到第一个大于pivot的元素
            self.arr[j] = self.arr[i]  # 交换
        self.arr[i] = pivot  # pivot 插入
        return i

    def quick_sort(self, left, right):  # 快速排序
        if left < right:
            mid = self.partition(left, right)
            self.quick_sort(left, mid - 1)
            self.quick_sort(mid + 1, right)

    def adjust_max_heap(self, dad, arr_len):
        """
        调整为大根堆
        """
        arr = self.arr
        son = 2 * dad + 1  # 左孩子索引
        while son < arr_len:
            if son + 1 < arr_len and arr[son] < arr[son + 1]:
                son += 1  # son 索引 孩子中的最大值
            if arr[dad] < arr[son]:
                arr[son], arr[dad] = arr[dad], arr[son]  # 使最大元素置于子树父节点位置
                dad = son  # 循环调整下面的子树
                son = son * 2 + 1
            else:  # 无需调整
                break

    def heap_sort(self):
        """
        堆排序
        """
        arr = self.arr
        for parent_pos in range(self.n // 2 - 1, -1, -1):  # 从最后一个父节点开始
            self.adjust_max_heap(parent_pos, self.n)  # 调整
        for end_pos in range(self.n - 1, 0, -1):
            arr[end_pos], arr[0] = arr[0], arr[end_pos]  # 交换堆顶和最后一个元素
            self.adjust_max_heap(0, end_pos)  # 剩余元素调整为大根堆

    def cal_time(self, sort_func, *args, **kwargs):  # 计算运行时间
        start = time.time()  # 距离1970年1月1日
        sort_func(*args, **kwargs)  # 回调函数(这里是检测函数)
        end = time.time()
        print(f"使用的排序时间为{end - start}")  # 持续时间=末-初


if __name__ == '__main__':
    s = Sort(100000, 100)
    # print(s.arr)
    # s.quick_sort(0, s.n-1)
    # print(s.arr)
    # s.heap_sort()
    # print(s.arr)
    s.cal_time(s.quick_sort, 0, s.n - 1)
    s.cal_time(s.heap_sort)
